// 默认props
const dProps = { id: "id", parentId: "parentId", children: "children" };

export function listToTree(list, props) {
  if (!Array.isArray(list)) {
    return [];
  }

  props = Object.assign({}, dProps, props);

  const map = list.reduce((map, item) => {
    map[item[props.id]] = item;
    return map;
  }, {});

  const root = new Set(list);

  list.forEach((item) => {
    let parent = map[item[props.parentId]];

    if (parent) {
      if (!parent[props.children]) {
        parent[props.children] = [];
      }
      parent[props.children].push(item);

      root.delete(item);
    }
  });

  return Array.from(root);
}

/**
 * 根据id从树中找项
 * @param tree
 * @param id
 * @param props 字段映射，主要是id跟children
 */
export function findTreeNodeById(tree, id, props) {
  if (!Array.isArray(tree)) {
    return null;
  }

  props = Object.assign({}, dProps, props);

  let item = null;

  treeForEach(
    tree,
    (node) => {
      if (node[props.id] === id) {
        item = node;

        return false; // 终止循环
      }
    },
    props
  );

  return item;
}

/**
 * 遍历树
 * @param tree
 * @param callback Fn(node, tree)  返回false 则跳出循环
 * @param props 字段映射，主要children
 * @param type 采用先序遍历:'1'，还是按层遍历: '3'
 * @return Array
 */
export function treeForEach(tree, callback, props, type) {
  if (!Array.isArray(tree) || !(callback instanceof Function)) {
    return tree;
  }
  props = Object.assign({}, dProps, props);

  const undo = [...tree];
  const walkedNode = new Set();

  while (undo.length > 0) {
    const node = undo.shift();
    const children = node[props.children] || [];
    const isWaked = walkedNode.has(node);

    if (type !== ForType.parentLast || children.length === 0 || isWaked) {
      let keepGoing = callback(node, tree);

      if (keepGoing === false) {
        break;
      }
      walkedNode.delete(node);
    } else {
      // 后序要塞回去
      undo.unshift(node);
      walkedNode.add(node);
    }

    if (children.length > 0 && !isWaked) {
      if (type === ForType.layer) {
        undo.push(...children);
      } else {
        undo.unshift(...children);
      }
    }
  }

  return tree;
}

export function treeForEachLast(tree, callback, props) {
  return treeForEach(tree, callback, props, ForType.parentLast);
}

// 遍历的类型
export const ForType = {
  parentFirst: "1", // 先序
  parentLast: "2", // 后序
  layer: "3", // 按层
};
